#include "biTree.h"
#include <malloc.h>
#include <stdio.h>
#include <string.h>

/**
 * 功 能：
 *      递归先序遍历
 * 参 数：
 *      node      ：要输出的节点
 *      pPrintFunc：输出节点值的回调函数
 * 返回值：
 *      无
 **/
static void __Bitree_prev_Older(BiTreeNode *node, BiTree_Printf *pPrintFunc) // O(n)
{
    if (node == NULL || pPrintFunc == NULL)
        return;

    pPrintFunc(node);
    __Bitree_prev_Older(node->lchild, pPrintFunc);
    __Bitree_prev_Older(node->rchild, pPrintFunc);
}
/**
 * 功 能：
 *      递归中序遍历
 * 参 数：
 *      node      ：要输出的节点
 *      pPrintFunc：输出节点值的回调函数
 * 返回值：
 *      无
 **/
static void __Bitree_in_Older(BiTreeNode *node, BiTree_Printf *pPrintFunc) // O(n)
{
    if (node == NULL || pPrintFunc == NULL)
        return;

    __Bitree_in_Older(node->lchild, pPrintFunc);
    pPrintFunc(node);
    __Bitree_in_Older(node->rchild, pPrintFunc);
}
/**
 * 功 能：
 *      递归后序遍历
 * 参 数：
 *      node      ：要输出的节点
 *      pPrintFunc：输出节点值的回调函数
 * 返回值：
 *      无
 **/
static void __Bitree_post_Older(BiTreeNode *node, BiTree_Printf *pPrintFunc) // O(n)
{
    if (node == NULL || pPrintFunc == NULL)
        return;

    __Bitree_post_Older(node->lchild, pPrintFunc);
    __Bitree_post_Older(node->rchild, pPrintFunc);
    pPrintFunc(node);
}

/**
 * 功 能：
 *      计算树的深度
 * 参 数：
 *      root ：要操作的树
 * 返回值：
 *      成功：树的深度
 *      失败：0
 **/
static int __BiTree_Depth(BiTreeNode *root) // O(n)
{
    int depth = 0;

    if (root != NULL)
    {
        int leftDepth = __BiTree_Depth(root->lchild);
        int rightDepth = __BiTree_Depth(root->rchild);

        depth = ((leftDepth > rightDepth) ? leftDepth : rightDepth) + 1;
    }

    return depth;
}

/**
 * 功 能：
 *      二叉树的递归遍历 - 第i层的遍历
 * 参 数：
 *      root      ：要遍历的树
 *      pPrintFunc：输出节点值的回调函数
 *      i         ：要遍历的层
 * 返回值：
 *      无 
 **/
void __layer_Older(BiTreeNode *root, BiTree_Printf *pPrintFunc, int i)
{
    if (root == NULL || i == 0 || pPrintFunc == NULL)
        return;

    if (i == 1)
    {
        pPrintFunc(root);
        return;
    }
    __layer_Older(root->lchild, pPrintFunc, i - 1);
    __layer_Older(root->rchild, pPrintFunc, i - 1);
}

/**
 * 功 能：
 *      递归层序遍历
 * 参 数：
 *      node      ：要输出的节点
 *      pPrintFunc：输出节点值的回调函数
 * 返回值：
 *      无
 **/
static void __Bitree_layer_Older(BiTreeNode *node, BiTree_Printf *pPrintFunc) // O(n)
{
    int i;
    if (node == NULL || pPrintFunc == NULL)
        return;

    int dep = __BiTree_Depth(node); // BTreeDepth(root);
    for (i = 1; i <= dep; i++)
    {
        __layer_Older(node, pPrintFunc, i);
    }
}

/**
 * 功 能：
 *      计算树中的节点的个数（ >=1 ）
 * 参 数：
 *      root ：要操作的树
 * 返回值：
 *      成功：节点的个数
 *      失败：0
 **/
static int BiTree_NodesCnt(BiTreeNode *root) // O(n)
{
    int nodes = 0;

    if (root == NULL)
        goto END;

    nodes = BiTree_NodesCnt(root->lchild) + BiTree_NodesCnt(root->rchild) + 1;

END:
    return nodes;
}

/**
 * 功 能：
 *      计算树的度
 * 参 数：
 *      root ：要操作的树
 * 返回值：
 *      成功：树的度
 *      失败：0
 **/
static int __BiTree_Degree(BiTreeNode *root) // O(n)
{
    int degree = 0;

    if (root == NULL)
        goto ERROR;
    /* 存在左子树，度加1 */
    if (root->lchild != NULL)
        degree++;

    /* 存在右子树，度加1 */
    if (root->rchild != NULL)
        degree++;

    /**
     *  如果度为1，说明只有一个子树（或左或右），那还需要判断子树的度是多少
     *  如果度不为1，则说明两种情况
     *      1.既存在左子树也存在右子树，此时度为2，为二叉树的最大的度
     *      2.既不存左子树在也不存在右子树，此时度为0
     **/
    if (degree == 1)
    {
        int leftDegree = __BiTree_Degree(root->lchild);
        int rightDegree = __BiTree_Degree(root->rchild);

        degree = degree > leftDegree ? degree : leftDegree;
        degree = degree > rightDegree ? degree : rightDegree;
    }

ERROR:
    return degree;
}

/**
 * 功 能：
 *      创建一个二叉树
 * 参 数：
 *      无
 * 返回值：
 *      成功：创建树的根节点
 *      失败：NULL
 **/
BiTree *BiTree_Create() // O(1)
{
    TBiTree *ret = NULL;

    ret = (TBiTree *)malloc(sizeof(TBiTree));

    if (ret == NULL)
        goto ERROR;

    memset(ret, 0, sizeof(TBiTree));

ERROR:
    return ret;
}

/**
 * 功 能：
 *      二叉树节点释放
 * 参 数：
 *      tree：要释放的二叉树
 * 返回值：
 *      无 
 **/
void BiTree_Release(BiTreeNode *tree)
{
    if (tree == NULL)
        return;

    // 递归释放左孩子节点
    if (tree->lchild != NULL)
    {
        BiTree_Release(tree->lchild);
        tree->lchild = NULL;
    }

    // 递归释放右孩子节点
    if (tree->rchild != NULL)
    {
        BiTree_Release(tree->rchild);
        tree->rchild = NULL;
    }

    // 释放根节点
    if (tree != NULL)
        tree = NULL;
}

/**
 * 功 能：
 *      销毁一个树
 * 参 数：
 *      tree：要操作的树
 * 返回值：
 *      无
 **/
void BiTree_Destroy(BiTree *tree) // O(1)
{
    if (tree == NULL)
        goto ERROR;

    TBiTree *BiTree = (TBiTree *)tree;

    BiTree_Release(BiTree->root);

ERROR:
    return;
}

/**
 * 功 能：
 *      清空一个树
 * 参 数：
 *      tree：要操作的树
 * 返回值：
 *      无
 **/
void BiTree_Clear(BiTree *tree) // O(1)
{
    TBiTree *BiTree = (TBiTree *)tree;

    if (BiTree != NULL)
    {
        BiTree_Release(BiTree->root);
        BiTree->count = 0;
        BiTree->root = NULL;
    }
}

/**
 * 功 能：
 *      插入节点
 * 参 数：
 *      tree ：要操作的树
 *      node ：要插入的节点
 *      pos  ：相对于根节点的位置（二进制表示）
 *      steps：移动的步数
 * 返回值：
 *      成功：0
 *      失败：-1
 **/
int BiTree_Insert(BiTree *tree, BiTreeNode *node, BiTNodePos pos, int steps) // O(n)
{
    TBiTree *BiTree = (TBiTree *)tree;
    int ret = 0, bit = 0;

    /* 判断参数异常 */
    if (BiTree == NULL || node == NULL || pos < 0 || steps < 0)
    {
        ret = -1;
        goto ERROR;
    }
    /* 临时指针，用于记录current移动的记录，初始化为NULL */
    BiTreeNode *parent = NULL;
    /* 从根节点出发，初始化为根节点，是要存入节点的位置 */
    BiTreeNode *current = BiTree->root;

    /* 对新加入的节点进行初始化，左子树和右子树为空 */
    node->lchild = NULL;
    node->rchild = NULL;

    /****
     * 定位节点的操作
     ****/
    /* 判断要拐的次数，并且current不能为NULL */
    while ((steps > 0) && (current != NULL))
    {
        /* 取pos的最低位与1进行与操作，可以确定是往左走还是往右走 */
        bit = pos & 1;
        /* pos右移 */
        pos = pos >> 1;
        /* 记录当前指针 */
        parent = current;
        /***
         *  由于在树中，有两个指针域，所以需要通过标志位来判断是往左走还是往右走 
         *  也是一条路走到底，类似于递归
         *  将线性的方法引进到树中，类似于链表的后移
         ***/
        if (bit == BiT_BRACH_L)
        {
            /* 向左转，类似于链表后移的操作 */
            current = current->lchild;
        }
        else if (bit == BiT_BRACH_R)
        {
            /* 向右转，同样类似于链表后移的操作 */
            current = current->rchild;
        }
        /* 操作次数进行--操作 */
        steps--;
    }

    /* 判断parent指针是否为空 */
    if (parent != NULL)
    {
        /**
         *  判断最后一次是从那边走过来的 
         *  如果是从左边走过来的：node节点指向partent的左子树
         **/
        if (bit == BiT_BRACH_L)
        {
            parent->lchild = node;
            /*** 
             * 当前位置是插入新节点的位置，
             * 如果是左边的子树，将当前节点的位置赋值给新插入节点的左子树 
             * 完成原来树中此节点后面的子树的链接操作
             ***/
            node->lchild = current;
        }
        else if (bit == BiT_BRACH_R)
        {
            /**
             *  判断最后一次是从那边走过来的
             *  如果是从右边走过来的：node节点指向partent的右子树
             **/
            parent->rchild = node;
            /*** 
             * 当前位置是插入新节点的位置，
             * 如果是右边的子树，将当前节点的位置赋值给新插入节点的右子树 
             * 完成原来树中此节点后面的子树的链接操作
             ***/
            node->rchild = current;
        }
    }
    else
    {
        /* 如果到这儿了，那么说明是插入的是根节点，那么就是将node赋值给root */
        BiTree->root = node;
    }
    /* 插入新节点，count进行自加操作 */
    BiTree->count++;

ERROR:
    return ret;
}

/**
 * 功 能：
 *      删除树中指定的节点
 * 参 数：
 *      tree ：要操作的树
 *      pos  ：相对于根节点的位置（二进制表示）
 *      steps：移动的步数
 * 返回值：
 *      成功：删除后的树的节点
 *      失败：NULL
 **/
BiTreeNode *BiTree_Delete(BiTree *tree, BiTNodePos pos, int steps) // O(n)
{
    BiTreeNode *current = NULL;

    if (tree == NULL || pos < 0 || steps < 0)
        goto ERROR;

    TBiTree *BiTree = (TBiTree *)tree;
    current = BiTree->root;
    if (current == NULL)
        goto ERROR;

    BiTreeNode *parent = NULL;
    int bit = 0;

    /* 判断要拐的次数，并且current不能为NULL */
    while ((steps > 0) && (current != NULL))
    {
        /* 取pos的最低位与1进行与操作，可以确定是往左走还是往右走 */
        bit = pos & 1;
        /* pos右移 */
        pos = pos >> 1;
        /* 记录当前指针 */
        parent = current;
        /***
         *  由于在树中，有两个指针域，所以需要通过标志位来判断是往左走还是往右走 
         *  也是一条路走到底，类似于递归
         *  将线性的方法引进到树中，类似于链表的后移
         ***/
        if (bit == BiT_BRACH_L)
        {
            /* 向左转，类似于链表后移的操作 */
            current = current->lchild;
        }
        else if (bit == BiT_BRACH_R)
        {
            /* 向右转，同样类似于链表后移的操作 */
            current = current->rchild;
        }
        /* 操作次数进行--操作 */
        steps--;
    }

    if (parent != NULL)
    {
        /* 最后一次操作是左转，那么将lchild指针置为空 */
        if (bit == BiT_BRACH_L)
            parent->lchild = NULL;
        /* 最后一次操作是右转，那么将rchild指针置为空 */
        else if (bit == BiT_BRACH_R)
            parent->rchild = NULL;
    }
    /* 如果parent为空，则说明要不就是一个节点，要不就是删除根节点，反正结果都是下面这样 */
    else
        BiTree->root = NULL;

    /* 将树的节点个数减去相对应的个数 */
    BiTree->count = BiTree->count - BiTree_NodesCnt(current);

ERROR:
    return current;
}

/**
 * 功 能：
 *      获取树中指定的节点
 * 参 数：
 *      tree ：要操作的树
 *      pos  ：相对于根节点的位置（二进制表示）
 *      steps：移动的步数
 * 返回值：
 *      成功：获取后的树的节点
 *      失败：NULL
 **/
BiTreeNode *BiTree_Get(BiTree *tree, BiTNodePos pos, int steps) // O(n)
{
    TBiTree *BiTree = (TBiTree *)tree;
    BiTreeNode *current = NULL; //BiTree->root;
    if (BiTree == NULL || pos < 0 || steps < 0)
        goto ERROR;

    int bit = 0;

    current = BiTree->root;
    if (current == NULL)
        goto ERROR;

    /* 判断要拐的次数，并且current不能为NULL */
    while ((steps > 0) && (current != NULL))
    {
        /* 取pos的最低位与1进行与操作，可以确定是往左走还是往右走 */
        bit = pos & 1;
        /* pos右移 */
        pos = pos >> 1;
        /***
         *  由于在树中，有两个指针域，所以需要通过标志位来判断是往左走还是往右走 
         *  也是一条路走到底，类似于递归
         *  将线性的方法引进到树中，类似于链表的后移
         ***/
        if (bit == BiT_BRACH_L)
        {
            /* 向左转，类似于链表后移的操作 */
            current = current->lchild;
        }
        else if (bit == BiT_BRACH_R)
        {
            /* 向右转，同样类似于链表后移的操作 */
            current = current->rchild;
        }
        /* 操作次数进行--操作 */
        steps--;
    }

ERROR:
    return current;
}

/**
 * 功 能：
 *      更新树中指定的节点
 * 参 数：
 *      tree   ：要操作的树
 *      pos    ：相对于根节点的位置（二进制表示）
 *      steps  ：移动的步数
 *      destVal: 要修改成的目标值, destVal 不得为 NULL
 * 返回值：
 *      成功：0
 *      失败：-1
 **/
int BiTree_Update(BiTree *tree, BiTNodePos pos, int steps, BiTreeNode *destVal) // O(n)
{
    BiTreeNode *current = NULL;
    int ret = -1;
    if (tree == NULL || destVal == NULL || pos < 0 || steps < 0)
        goto ERROR;

    TBiTree *BiTree = (TBiTree *)tree;
    current = BiTree->root;
    if (current == NULL)
        goto ERROR;

    int bit = 0;

    BiTreeNode *parent = NULL;
    /* 判断要拐的次数，并且current不能为NULL */
    while ((steps > 0) && (current != NULL))
    {
        /* 取pos的最低位与1进行与操作，可以确定是往左走还是往右走 */
        bit = pos & 1;
        /* pos右移 */
        pos = pos >> 1;
        /* 记录当前指针 */
        parent = current;
        /***
         *  由于在树中，有两个指针域，所以需要通过标志位来判断是往左走还是往右走 
         *  也是一条路走到底，类似于递归
         *  将线性的方法引进到树中，类似于链表的后移
         ***/
        if (bit == BiT_BRACH_L)
        {
            /* 向左转，类似于链表后移的操作 */
            current = current->lchild;
        }
        else if (bit == BiT_BRACH_R)
        {
            /* 向右转，同样类似于链表后移的操作 */
            current = current->rchild;
        }
        /* 操作次数进行--操作 */
        steps--;
    }
    /* 如果current为空，则说明要替换的节点不存在 */
    if (current == NULL)
    {
        goto ERROR;
    }

    /* 判断parent指针是否为空，类似于插入的操作 */
    if (parent != NULL)
    {
        if (bit == BiT_BRACH_L)
        {
            parent->lchild = destVal;
        }
        else if (bit == BiT_BRACH_R)
        {
            parent->rchild = destVal;
        }
    }
    else
    {
        /* 如果到这儿了，那么说明是根节点 */
        BiTree->root = destVal;
    }
    /* 将当前找到的节点的值修改成目标值，将旧节点的子树赋值给目标节点的子树 */
    destVal->lchild = current->lchild;
    destVal->rchild = current->rchild;
    /* 修改ret值 */
    ret = 0;

ERROR:
    return ret;
}

/**
 * 功 能：
 *      获取树中的根节点
 * 参 数：
 *      tree ：要操作的树
 * 返回值：
 *      成功：获取后的树的节点
 *      失败：NULL
 **/
BiTreeNode *BiTree_Root(BiTree *tree) // O(1)
{
    TBiTree *BiTree = (TBiTree *)tree;
    return BiTree == NULL ? NULL : BiTree->root;
}

/**
 * 功 能：
 *      获取树中的深度/高度
 * 参 数：
 *      tree ：要操作的树
 * 返回值：
 *      成功：获取后的树的节点
 *      失败：NULL
 **/
int BiTree_Depth(BiTree *tree) // O(n)
{
    TBiTree *BiTree = (TBiTree *)tree;

    return BiTree == NULL ? -1 : __BiTree_Depth(BiTree->root);
}

/**
 * 功 能：
 *      获取树中的节点的个数
 * 参 数：
 *      tree ：要操作的树
 * 返回值：
 *      成功：节点的个数
 *      失败：-1
 **/
int BiTree_Count(BiTree *tree) // O(1)
{
    TBiTree *BiTree = (TBiTree *)tree;

    return BiTree == NULL ? -1 : BiTree->count;
}
/**
 * 功 能：
 *      获取树中的度
 * 参 数：
 *      tree ：要操作的树
 * 返回值：
 *      成功：树的度
 *      失败：-1
 **/
int BiTree_Degree(BiTree *tree) // O(n)
{
    TBiTree *BiTree = (TBiTree *)tree;

    return BiTree == NULL ? -1 : __BiTree_Degree(BiTree->root);
}

/**
 * 功 能：
 *      打印树中的内容
 * 参 数：
 *      tree      ：要操作的树
 *      pPrintFunc：输出节点值的回调函数
 *      chl       ：选择遍历的方式，默认为先序遍历
 *          0：先序遍历
 *          1：中序遍历
 *          2：后序遍历
 *          3：层序遍历
 * 返回值：
 *      无
 **/
void BiTree_Display(BiTree *tree, BiTree_Printf *pPrintFunc, int chl) // O(n)
{
    TBiTree *BiTree = (TBiTree *)tree;

    if (BiTree == NULL)
        goto ERROR;

    switch (chl)
    {
    case 1:
        __Bitree_in_Older(BiTree->root, pPrintFunc);
        break;
    case 2:
        __Bitree_post_Older(BiTree->root, pPrintFunc);
        break;
    case 3:
        __Bitree_layer_Older(BiTree->root, pPrintFunc);
        break;
    default:
        __Bitree_prev_Older(BiTree->root, pPrintFunc);
        break;
    }

ERROR:
    printf("\n");
    return;
}

TFBiTree fBiTree = {
    BiTree_Create,
    BiTree_Insert,
    BiTree_Delete,
    BiTree_Get,
    BiTree_Update,
    BiTree_Display,
    BiTree_Clear,
    BiTree_Depth,
    BiTree_Count,
    BiTree_Degree,
    BiTree_Root,
    BiTree_Destroy};
